ARC105 C Camels and Bridge
まず, どのようにしても橋が崩落してしまうのは$ min \{v_i\} < max\{w_i\}のときである.
そのまますべての橋が崩落しないか試していては$ O(N! M)となってしまい, 間に合わない. $ Mの部分の計算量を落とすことを考える. すると, 二分探索という解法が思いつく. 具体的には長さ, 耐荷重の2つの情報を持たせた2つのpair配列を考え, 橋が崩落しないうちの最小の耐荷重を求め, その重さ以下の最大の長さを前計算により求めておく. こうすることでDPによって$ O(N! N^2)でこの問題を解くことができる.